
Namespace std
    'really need to make a circle?
    Public Class list(Of valueT)
#If RETIRED Then
        Inherits IComparable2(Of list(Of valueT))
#End If
        Implements linearContainer(Of valueT), IComparable(Of list(Of valueT)), IComparable

        Public Class iterator
            Inherits randomAccessIterator(Of node)
            Implements container(Of valueT).iterator

            Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
                If Not p Is Nothing Then
                    If prev Then
                        p = p.last
                    Else
                        p = p.next
                    End If

                    Return Me <> _end
                Else
                    Return False
                End If
            End Function

            Public Sub New()
                MyBase.New()
            End Sub

            Public Sub New(ByVal that As pointer(Of node))
                MyBase.New(that)
            End Sub

            Public Sub New(ByVal that As node)
                MyBase.New(that)
            End Sub

            Public Overloads Shared Operator +(ByVal this As iterator) As valueT
                Return ++convertor.cast(Of pointer(Of node))(this)
            End Operator

            Public Overloads Function instance() As valueT Implements container(Of valueT).iterator.instance
                Return MyBase.instance()
            End Function
        End Class

        Public Class node
            Inherits pointernode(Of valueT)

            Private Const _pointerCount As Int64 = 2

            Private Class pointerIndex
                Public Const last As Int64 = 0
                Public Const [next] As Int64 = 1
            End Class

            Public Function last() As node
                Return pointer(pointerIndex.last)
            End Function

            Public Function [next]() As node
                Return pointer(pointerIndex.next)
            End Function

            Public Sub appendlast(ByVal that As node)
                debugassert(Not Object.ReferenceEquals(Me, that), "should not append last to a node itself.")
                pointer(pointerIndex.last) = that
                If Not that Is Nothing Then
                    that.pointer(pointerIndex.next) = Me
                End If
            End Sub

            Public Sub appendnext(ByVal that As node)
                debugassert(Not Object.ReferenceEquals(Me, that), "should not append next to a node itself.")
                pointer(pointerIndex.next) = that
                If Not that Is Nothing Then
                    that.pointer(pointerIndex.last) = Me
                End If
            End Sub

            Public Sub New()
                MyBase.New(_pointerCount)
            End Sub

            Public Sub New(ByVal newData As valueT)
                MyBase.New(_pointerCount, newData)
            End Sub
        End Class

        Private Shared _end As iterator = Nothing
        Private _front As node
        Private _back As node
        Private _size As Int64

        Public Function begin() As iterator
            Return New iterator(_front)
        End Function

        Public Function container_iterator_begin() As container(Of valueT).iterator _
            Implements linearContainer(Of valueT).begin
            Return begin()
        End Function

        Public Function rbegin() As iterator
            Return New iterator(_back)
        End Function

        Public Function container_iterator_rbegin() As container(Of valueT).iterator _
            Implements linearContainer(Of valueT).rbegin
            Return rbegin()
        End Function

        Public Function [end]() As iterator
            Return _end
        End Function

        Public Function container_iterator_end() As container(Of valueT).iterator _
            Implements linearContainer(Of valueT).end
            Return [end]()
        End Function

        Public Function rend() As iterator
            Return _end
        End Function

        Public Function container_iterator_rend() As container(Of valueT).iterator _
            Implements linearContainer(Of valueT).rend
            Return rend()
        End Function

        Public Property front() As valueT Implements linearContainer(Of valueT).front
            Get
                Return +_front
            End Get
            Set(ByVal value As valueT)
                _front.data = value
            End Set
        End Property

        Public Property back() As valueT Implements linearContainer(Of valueT).back
            Get
                Return +_back
            End Get
            Set(ByVal value As valueT)
                _back.data = value
            End Set
        End Property

        Public Property first() As valueT
            Get
                Return +_front
            End Get
            Set(ByVal value As valueT)
                If Not empty() Then
                    copy(_front.data, value)
                End If
            End Set
        End Property

        Public Property last() As valueT
            Get
                Return +_back
            End Get
            Set(ByVal value As valueT)
                If Not empty() Then
                    copy(_back.data, value)
                End If
            End Set
        End Property

        Private Function find(ByVal index As Int64) As node
            Dim rtn As node = Nothing
            If Not availableIndex(index) Then
                rtn = Nothing
            Else
                If index <= _size \ 2 Then
                    rtn = _front
                    While index > 0
                        rtn = rtn.next
                        index -= 1
                    End While
                Else
                    rtn = _back
                    index = _size - index - 1
                    While index > 0
                        rtn = rtn.last
                        index -= 1
                    End While
                End If
            End If

            Return rtn
        End Function

        Public Function [goto](ByVal index As Int64) As iterator
            Return New iterator(find(index))
        End Function

        Public Function find(ByVal v As valueT) As iterator
            Dim it As iterator = Nothing
            it = begin()
            While it <> [end]()
                If compare(v, +it) = 0 Then
                    Return it
                End If

                it += 1
            End While

            Return [end]()
        End Function

        Public Function rfind(ByVal v As valueT) As iterator
            Dim it As iterator = Nothing
            it = rbegin()
            While it <> rend()
                If compare(v, +it) = 0 Then
                    Return it
                End If

                it -= 1
            End While

            Return rend()
        End Function

        Public Function availableIndex(ByVal index As Int64) As Boolean
            Return index >= 0 And index < size()
        End Function

        Public Function size() As Int64 Implements linearContainer(Of valueT).size
            Return _size
        End Function

        Default Public Property at(ByVal index As Int64) As valueT Implements linearContainer(Of valueT).at
            Get
                Dim rtn As node = Nothing
                rtn = find(index)
                Return +rtn
            End Get
            Set(ByVal value As valueT)
                Dim rtn As node = Nothing
                rtn = find(index)
                If Not rtn Is Nothing Then
                    copy(rtn.data, value)
                End If
            End Set
        End Property

        Public Function empty() As Boolean Implements linearContainer(Of valueT).empty
            Return size() = 0
        End Function

        Public Function push_back(ByVal newData As valueT) As Boolean Implements linearContainer(Of valueT).push_back
            Dim add As node = Nothing
            add = New node(newData)
            If Not _back Is Nothing Then
                _back.appendnext(add)
            Else
                _front = add
            End If
            _back = add
            _size += 1

            Return True
        End Function

        Public Function push_front(ByVal newData As valueT) As Boolean Implements linearContainer(Of valueT).push_front
            Dim add As node = Nothing
            add = New node(newData)
            If Not _front Is Nothing Then
                _front.appendlast(add)
            Else
                _back = add
            End If
            _front = add
            _size += 1

            Return True
        End Function

        Public Function pop_back() As Boolean Implements linearContainer(Of valueT).pop_back
            If empty() Then
                Return False
            Else
                Dim it As node = _back
                [erase](it)
                Return True
            End If
        End Function

        Public Function pop_front() As Boolean Implements linearContainer(Of valueT).pop_front
            If empty() Then
                Return False
            Else
                Dim it As node = _front
                [erase](it)
                Return True
            End If
        End Function

        Public Function insert(ByVal it As iterator, ByVal newdata As valueT) As iterator
            Return insert(+convertor.cast(Of pointer(Of node))(it), newdata)
        End Function

        Private Function insert(ByVal it As node, ByVal newData As valueT) As iterator
            Dim work As node = Nothing
            If it Is Nothing Then
                Return [end]()
            Else
                work = New node(newData)
                'it.next will be changed after work.appendlast(it)
                work.appendnext(it.next)
                work.appendlast(it)
                If Object.ReferenceEquals(it, _back) Then
                    _back = work
                End If
                _size += 1
                it = it.next()
                debugassert(Not it Is Nothing, "it.next() is nothing after insert.")

                Return New iterator(it)
            End If
        End Function

        Public Function insert(ByVal index As Int64, ByVal newData As valueT) As iterator
            Return insert(find(index), newData)
        End Function

        Public Function insert(ByVal newData As valueT) As container(Of valueT).iterator _
                                                                                Implements container(Of valueT).insert
            push_back(newData)
            Return rbegin()
        End Function

        Private Function [erase](ByRef it As node) As iterator
            If it Is Nothing Then
                Return [end]()
            Else
                Dim del As node = it
                If Not it.last Is Nothing Then
                    it.last.appendnext(it.next)
                ElseIf Not it.next Is Nothing Then
                    it.next.appendlast(it.last)
                End If
                If Object.ReferenceEquals(it, _front) Then
                    _front = it.next
                End If
                If Object.ReferenceEquals(it, _back) Then
                    _back = it.last
                End If
                If Not it Is Nothing Then
                    it = it.next
                Else
                    it = Nothing
                End If
                _size -= 1
                del.appendlast(Nothing)
                del.appendnext(Nothing)
                Return New iterator(it)
            End If
        End Function

        Public Function [erase](ByRef it As iterator) As iterator
            Return [erase](+convertor.cast(Of pointer(Of node))(it))
        End Function

        Public Function [erase](ByVal index As Int64) As iterator
            Return [erase](find(index))
        End Function

        Public Function [erase](ByVal s As valueT) As iterator
            Return [erase](find(s))
        End Function

        Public Sub clear() Implements linearContainer(Of valueT).clear
#If RETIRED Then
            Dim it As node = _front
            While Not it Is Nothing
                [erase](it)
            End While
#End If
            _front = Nothing
            _back = Nothing
            _size = 0
        End Sub

        Public Function Clone() As Object Implements linearContainer(Of valueT).Clone
            Dim rtn As list(Of valueT) = Nothing
            Dim it As list(Of valueT).node
            rtn = alloc(Me)
            it = _front
            While Not it Is Nothing
                rtn.push_back(it.data)
                it = it.next
            End While

            Return rtn
        End Function

        Shared Sub New()
            _end = New iterator(convertor.cast(Of node)(Nothing))
        End Sub

        Public Sub New()
            clear()
        End Sub

        Public Function contains(ByVal v As valueT) As Boolean
            Return find(v) <> [end]()
        End Function

        Public Function CompareTo(ByVal that As list(Of valueT)) As Int32 _
                                                                    Implements IComparable(Of list(Of valueT)).CompareTo
            assert(Not that Is Nothing, "that should not be nothing after inherits from IComparable2.")

            Dim i As list(Of valueT).iterator = Nothing
            Dim j As list(Of valueT).iterator = Nothing

            i = begin()
            j = that.begin()
            While i <> [end]() AndAlso j <> that.end()
                Dim cmp As Int32
                cmp = compare(+convertor.cast(Of pointer(Of node))(i), +convertor.cast(Of pointer(Of node))(j))
                If cmp <> 0 Then
                    Return cmp
                End If

                i += 1
                j += 1
            End While

            If i = [end]() AndAlso j = that.end() Then
                Return 0
            ElseIf i = [end]() Then
                Return -1
            Else
                Return 1
            End If
        End Function

        Public Function CompareTo(ByVal that As Object) As Int32 Implements IComparable.CompareTo
            Return CompareTo(convertor.cast(Of list(Of valueT))(that, False))
        End Function

        Public Shared Operator =(ByVal this As list(Of valueT), ByVal that As list(Of valueT)) As Boolean
            Return operatorEqual(this, that)
        End Operator

        Public Shared Operator <>(ByVal this As list(Of valueT), ByVal that As list(Of valueT)) As Boolean
            Return operatorUnequal(this, that)
        End Operator

        Public Shared Operator =(ByVal this As list(Of valueT), ByVal that As Object) As Boolean
            Return operatorEqual(this, that)
        End Operator

        Public Shared Operator <>(ByVal this As list(Of valueT), ByVal that As Object) As Boolean
            Return operatorUnequal(this, that)
        End Operator

        Public Shared Function emptyToString(ByVal it As randomAccessIterator(Of node)) As String
            Return Convert.ToString(++it)
        End Function

        Public Overloads Function ToString(ByVal startIndex As Int64, ByVal f As operators.ToStringMethod(Of node), _
                                           Optional ByVal seperator As String = character.tab) As String
            Return operators.ToString(Of node, iterator)(f, [goto](startIndex), [end](), seperator)
        End Function

        Public Overloads Function ToString(ByVal f As operators.ToStringMethod(Of node), _
                                           Optional ByVal seperator As String = character.tab) As String
            Return operators.ToString(Of node, iterator)(f, begin(), [end](), seperator)
        End Function

        Public Overloads Function ToString(ByVal startIndex As Int64, _
                                           Optional ByVal seperator As String = character.tab) As String
            Return ToString(startIndex, AddressOf emptyToString, seperator)
        End Function

        Public Overloads Function ToString(ByVal seperator As String) As String
            Return ToString(AddressOf emptyToString, seperator)
        End Function

        Public Overrides Function ToString() As String
            Return ToString(character.tab)
        End Function

        Private Class unittestInfo
            Public d As list(Of valueT) = Nothing
            Public v As vector(Of valueT) = Nothing

            Public Sub New()
                d = New list(Of valueT)()
                v = New vector(Of valueT)()
            End Sub
        End Class

        Private Class unittestActions
            Private Shared Sub parseParameter(ByVal obj As Object _
                                              , ByRef d As list(Of String), ByRef v As vector(Of String))
                Dim info As list(Of String).unittestInfo = Nothing
                info = convertor.cast(Of list(Of String).unittestInfo)(obj)

                d = info.d
                v = info.v

                assert(Not d Is Nothing, "d is nothing.")
                assert(Not v Is Nothing, "v is nothing.")
            End Sub

            Public Shared Sub first(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element in list
                d.push_back(createGUID())
                v.push_back(d.last())

                assert(v.erase(d.first()), "cannot find first element of list in vector.")
                d.first() = createGUID()
                raiseError("change first to " + d.first())
                v.push_back(d.first())
            End Sub

            Public Shared Sub last(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element in list
                d.push_front(createGUID())
                v.push_back(d.first())

                assert(v.erase(d.last()), "cannot find last element of list in vector.")
                d.last() = createGUID()
                raiseError("change last to " + d.last())
                v.push_back(d.last())
            End Sub

            Public Shared Sub insert(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                If Not v.empty() Then
                    Dim s As String = Nothing
                    s = v(rnd(0, v.size(), True))

                    Dim it As list(Of String).iterator = Nothing
                    If rnd(0, 2, True) = 0 Then
                        it = d.find(s)
                        assert(it <> d.end(), "cannot find " + s + " in list.")
                    Else
                        it = d.rfind(s)
                        assert(it <> d.rend(), "cannot find " + s + " in list.")
                    End If

                    it = d.insert(it, createGUID())
                    raiseError("insert " + +it + " next to " + s)
                    v.push_back(+it)
                Else
                    raiseError("insert but empty")
                    assert(d.empty(), "d.empty() <> v.empty().")
                End If
            End Sub

            Public Shared Sub push_back(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                Dim s As String = Nothing
                s = createGUID()
                raiseError("push_back " + s)
                d.push_back(s)
                assert(strsame(d.last(), s), "d.push_back(" + s + ") <> d.last()")
                v.push_back(s)
            End Sub

            Public Shared Sub push_front(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                Dim s As String = Nothing
                s = createGUID()
                raiseError("push_front " + s)
                d.push_front(s)
                assert(strsame(d.first(), s), "d.push_front(" + s + ") <> d.first()")
                v.push_back(s)
            End Sub

            Public Shared Sub pop_front(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element in list
                d.push_back(createGUID())
                v.push_back(d.last())
                v.erase(d.first())
                raiseError("pop_front")
                d.pop_front()
            End Sub

            Public Shared Sub pop_back(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element in list
                d.push_front(createGUID())
                v.push_back(d.first())
                v.erase(d.last())
                raiseError("pop_back")
                d.pop_back()
            End Sub

            Public Shared Sub size(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                raiseError("size")
                assert(d.size() = v.size(), "d.size() <> v.size()")

                Dim it As list(Of String).iterator = Nothing
                it = d.begin()
                Dim count As Int64
                count = 0
                While it <> d.end()
                    count += 1
                    it += 1
                End While
                assert(d.size() = count, "d.size() <> count")
            End Sub

            Public Shared Sub empty(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                raiseError("empty")
                assert(d.empty() = v.empty(), "d.empty() <> v.empty()")
            End Sub

            Public Shared Sub find(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element.
                d.push_back(createGUID())
                v.push_back(d.last())

                Dim s As String = Nothing
                s = v(rnd(0, v.size(), True))
                raiseError("find " + s)
                assert(d.find(s) <> d.end(), "d.find(" + s + ") = d.end()")
            End Sub

            Public Shared Sub rfind(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element.
                d.push_front(createGUID())
                v.push_back(d.first())

                Dim s As String = Nothing
                s = v(rnd(0, v.size(), True))
                raiseError("rfind " + s)
                assert(d.rfind(s) <> d.rend(), "d.rfind(" + s + ") = d.rend()")
            End Sub

            Public Shared Sub at(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                'confirm at least one element.
                d.push_back(createGUID())
                v.push_back(d.last())

                Dim i As Int64 = Nothing
                i = rnd(0, d.size(), True)
                assert(v.erase(d(i)), "v.erase(" + d(i) + ") returns false.")
                d(i) = createGUID()
                raiseError("change " + Convert.ToString(i) + " to " + d(i))
                v.push_back(d(i))
            End Sub

            Public Shared Sub [erase](ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                If Not v.empty() Then
                    Dim i As Int64 = Nothing
                    If rnd(0, 2, True) = 0 Then
                        i = rnd(0, v.size(), True)
                        raiseError("erase " + v(i))
                        d.erase(v(i))
                        assert(v.erase(v(i)), "cannot find " + v(i) + " in vector.")
                    Else
                        i = rnd(0, d.size(), True)
                        Dim s As String = Nothing
                        s = d(i)
                        raiseError("erase index " + Convert.ToString(i) + " data " + s)
                        d.erase(i)
                        assert(v.erase(s), "cannot find " + s + " in vector.")
                    End If
                Else
                    raiseError("erase but empty")
                    assert(d.empty(), "d.empty() <> v.empty()")
                End If
            End Sub

            Public Shared Sub clone(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                raiseError("clone")
                Dim d2 As list(Of String) = Nothing
                copy(d2, d)
                assert(Not Object.ReferenceEquals(d, d2), "d2 is the same object as d.")
                assert(compare(d, d2) = 0, "d<>d2 after clone.")
            End Sub

            Public Shared Sub clear(ByVal obj As Object)
                Dim d As list(Of String) = Nothing
                Dim v As vector(Of String) = Nothing

                parseParameter(obj, d, v)

                d.clear()
                v.clear()

                raiseError("clear")
                assert(d.empty(), "d.empty()=false after clear.")
            End Sub
        End Class

        Public Shared Sub automaticalUnittest()
            Dim roundcount As Int64 = 10240
            If isreleasebuild() Then
                roundcount *= 20
            End If

            raiseError("********* list(of string) automatcial unittest *********", errorHandle.errorType.application)

            Dim info As unittestInfo = Nothing
            info = New unittestInfo()
            randomrun.invoke(roundcount, info _
                             , New randomrun.info(0.05, AddressOf unittestActions.first) _
                             , New randomrun.info(0.05, AddressOf unittestActions.last) _
                             , New randomrun.info(0.12, AddressOf unittestActions.insert) _
                             , New randomrun.info(0.13, AddressOf unittestActions.push_back) _
                             , New randomrun.info(0.13, AddressOf unittestActions.push_front) _
                             , New randomrun.info(0.05, AddressOf unittestActions.pop_back) _
                             , New randomrun.info(0.05, AddressOf unittestActions.pop_front) _
                             , New randomrun.info(0.05, AddressOf unittestActions.size) _
                             , New randomrun.info(0.05, AddressOf unittestActions.empty) _
                             , New randomrun.info(0.1, AddressOf unittestActions.find) _
                             , New randomrun.info(0.1, AddressOf unittestActions.rfind) _
                             , New randomrun.info(0.05, AddressOf unittestActions.at) _
                             , New randomrun.info(0.05, AddressOf unittestActions.erase) _
                             , New randomrun.info(0.01, AddressOf unittestActions.clone) _
                             , New randomrun.info(0.01, AddressOf unittestActions.clear))

            While Not info.d.empty()
                unittestActions.erase(info)
            End While

            raiseError("************** finish automatical unittest **************", errorHandle.errorType.application)
        End Sub
    End Class
End Namespace
